/*
	Colored Trails
	
	Copyright (C) 2006-2007, President and Fellows of Harvard College.  All Rights Reserved.
	
	This program is free software; you can redistribute it and/or
	modify it under the terms of the GNU General Public License
	as published by the Free Software Foundation; either version 2
	of the License, or (at your option) any later version.
	
	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.
	
	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
*/

package ctexpsupport.dudi;
import java.util.ArrayList;
import java.util.List;
import java.util.*;

public class Problem {

	public ArrayList<Target> goals=new ArrayList<Target>();
	int GoalsCounter=0;
	public List<Precedence> precedences=new ArrayList<Precedence>();
	
	public Problem clone()
	{
		Problem problem=new Problem();
		problem.goals=cloneGoalsArray(this.goals);
		problem.GoalsCounter=this.GoalsCounter;
		problem.precedences=this.precedences;
		return problem;
	}
	
	public int getPositionInPathByID(ArrayList<Target> goals,int id)
	{
		for(int i=0;i<goals.size();i++) if (goals.get(i).goalID==id) return i;
		return -1;
	}
	
	public ArrayList<Target> cloneGoalsArray(ArrayList<Target> goals)
	{
		//ArrayList<Goal> result=new ArrayList<Goal>();
		ArrayList<Target> result=(ArrayList)goals.clone();
		//for(int i=0;i<goals.size();i++) result.add(goals.get(i));
		return result;
	}
	
	public void addTarget(int xPos,int yPos,int value,int decreaseRate)
	{
		Target goal=new Target(new Position(xPos,yPos),value,GoalsCounter++,decreaseRate);
		goals.add(goal);
	}
	
	public void addTarget(Target goal)
	{
		goals.add(goal);
		GoalsCounter++;
	}
	

	public boolean someoneInWay(Position source,Position destination,ArrayList<Target> goals)
	{
		Position goalPosition;
		int minX=Math.min(source.xPos,destination.xPos);
		int minY=Math.min(source.yPos,destination.yPos);
		int maxY=Math.max(source.yPos,destination.yPos);
		int maxX=Math.max(source.xPos,destination.xPos);
		
		for(int i=0;i<goals.size();i++)
		{
			goalPosition=goals.get(i).position;
			if((goalPosition.xPos<=maxX)&&(goalPosition.xPos>=minX)&&(goalPosition.yPos<=maxY)&&(goalPosition.yPos>=minY))
				return true;
		}
		return false;
	}
	
	public void addPrecedences(int from,int to)
	{
		Precedence precedence=new Precedence(from,to);
		precedences.add(precedence);
	}
	
	//checks if goal can be accessed given the precedences 
	public boolean canBeAccessed(Target goal,ArrayList<Target> goals)
	{
		if(goal.conditionedByID<0) return true;
		for(int i=0;i<goals.size();i++) 
			if(goal.conditionedByID==goals.get(i).goalID) return false;
		return true;
	}

	public int getDistance(Position source,Position destination)
	{
		return(Math.abs(source.xPos-destination.xPos)+Math.abs(source.yPos-destination.yPos));
	}
	
	public int getValue(ArrayList<Target> goals,Position position,int time,boolean log)
	{
		if (log) 
		{
			MainProgram.writeLog.writeln(">>>GetValue: ");
			printGoals2File(goals,time);
		}
		int sum=0;
		int steps=0;
		for(int i=0;i<goals.size();i++) 
		{
			Target goal=goals.get(i);
			steps+=getDistance(goal.position,position);
			sum=sum+Math.max(goal.value-(steps+time)*goal.marginalValueDecrease,0);
			position=goal.position;
			if (log) MainProgram.writeLog.write("[goal "+goal.goalID+" Accumulated "+(goal.value-(steps+time)*goal.marginalValueDecrease)+"->"+Math.max(goal.value-(steps+time)*goal.marginalValueDecrease,0)+"]");
			//System.out.print("[Distance: "+steps+","+" time: "+time+" ValueDec: "+goals.get(plan[i]).marginalValueDecrease+"]");
		}
		if (log) MainProgram.writeLog.writeln("");
		//System.out.print(" [Value returned: " +" ["+position.xPos+","+position.yPos+"] to ");
		//printSolution(goals);
		//System.out.print("[Value returned: "+sum+"]");
		return sum;
	}
	
	
	public ArrayList<Target> bestPath(ArrayList<Target> goals,Position position,int time)
	{
		boolean debugThisFunction=false;
		
		ArrayList<Target> result=new ArrayList<Target>();
		
		if(debugThisFunction)
		{
			MainProgram.writeLog.writeln("Entering best path.");
			MainProgram.writeLog.writeln("Goals are:");
			printGoals2File(goals,time);
		}
		if (goals.size()==1) 
		{
			result.add(goals.get(0));
			if(debugThisFunction)
			{
				MainProgram.writeLog.writeln("Only one target remained.");
				MainProgram.writeLog.writeln("Returning goal: "+result.get(0).goalID);
				printGoals2File(goals,time);
			}
			return result;
		}
		ArrayList<Target> subSolution=null;
		ArrayList<Target> bestSubSolution=null;
		
		int bestMove=0;
		double bestMoveValue=-1000;
		double currentMoveValue;
		
		for(int i=0;i<goals.size();i++)
		{
			MainProgram.writeLog.writeln("Evaluating going next from "+position.xPos+","+position.yPos+" to "+goals.get(i).goalID+" [for element "+(this.goals.size()-goals.size()+1)+"]");
			//System.out.print("Checking for Goal: "+goals.get(i).goalID+"("+goals.size()+")");
			subSolution=(ArrayList)goals.clone();
			//if we go to i then we need to adjust clock
			int distance=getDistance(position,goals.get(i).position);
			currentMoveValue=Math.max(subSolution.get(i).value-(distance+time)*subSolution.get(i).marginalValueDecrease,0);
			//now remove the element that was assigned to be next
			subSolution.remove(i);
			if((!someoneInWay(position,goals.get(i).position,subSolution))&&(canBeAccessed(goals.get(i),subSolution)))
			{
				subSolution=bestPath(subSolution,goals.get(i).position,time+distance);
				if(debugThisFunction)
				{
					MainProgram.writeLog.writeln("BestPath received: "+path2String(subSolution));
				}				
				currentMoveValue=currentMoveValue+getValue(subSolution,goals.get(i).position,time+distance,false);
				//System.out.println();
				//System.out.println(" Value is: "+currentMoveValue);
				if (currentMoveValue>bestMoveValue)
				{
					
					bestMoveValue=currentMoveValue;
					bestMove=i;
					bestSubSolution=(ArrayList)subSolution.clone();
				}
				//printSolution(goals);
			}
			else if(someoneInWay(position,goals.get(i).position,subSolution))
			{
				MainProgram.writeLog.writeln("Someone was in the way to get from "+position.xPos+","+position.yPos+" to "+goals.get(i).goalID);
			}
			else if(canBeAccessed(goals.get(i),subSolution))
			{
				MainProgram.writeLog.writeln("Cannot be accessed "+i);
			}
			else if(canBeAccessed(goals.get(i),subSolution))
			{
				System.out.print("We have a problem here [1] ");
			}
		}
		if (bestSubSolution==null)
		{
			printGoals2File(goals,time);
		}
		bestSubSolution.add(0,goals.get(bestMove));
		MainProgram.writeLog.writeln("Returned Path: "+path2String(bestSubSolution)+" Value: "+bestMoveValue);
		//System.out.print("\nBest sub solutionis: "+goals.get(bestMove).goalID+"->");
		//printSolution(solution);
		//System.out.println("");
		return bestSubSolution;
	}

	
	public void printSolution(ArrayList<Target> goals,int output)
	{
		for(int i=0;i<goals.size();i++) 
		{
			if (output==1) System.out.print(goals.get(i).goalID+"("+goals.get(i).value+")->");
			else MainProgram.writeLog.write(goals.get(i).goalID+"("+goals.get(i).value+")->");
		}		
		if (output==1) System.out.println("");
		else MainProgram.writeLog.writeln("");
	}
	
	//Returns the two possible moves the player is likely to move next (based on two possible optimal ways to get from point A to point B. If player and target are at the same row or column then returns only one
	public ArrayList<Position> expectedMoves(Position position, Target target)
	{
		int xDirection,yDirection;
		ArrayList<Position> positions=new ArrayList<Position>();
		if (position.xPos>target.position.xPos)
			xDirection=-1;
		else if (position.xPos<target.position.xPos)
			xDirection=1;
		else xDirection=0;
		if (position.yPos>target.position.yPos)
			yDirection=-1;
		else if (position.yPos<target.position.yPos)
			yDirection=1;
		else yDirection=0;
		if (xDirection!=0)
		{
			Position position1=position.clone();
			position1.xPos+=xDirection;
			positions.add(position1);
		}
		if (yDirection!=0)
		{
			Position position2=position.clone();
			position2.yPos+=yDirection;
			positions.add(position2);
		}
		return positions;
	}
	
	//Generate all possible changes
	public ArrayList<ChangesSet> generateChangeValues(Position position,int time)
	{
		MainProgram.writeLog.writeln("Generating Value Changes:");
		ArrayList<ChangesSet> changes=new ArrayList<ChangesSet>();
		ArrayList<Target> currentPath=bestPath(goals,position,time);
		for(int firstTarget=0;firstTarget<goals.size();firstTarget++)
		{
			for(int secondTarget=firstTarget+1;secondTarget<goals.size();secondTarget++)
			{
				for(int directionFirst=-1;directionFirst<2;directionFirst=directionFirst+2)
				{
					for(int directionSecond=-1;directionSecond<2;directionSecond=directionSecond+2)
					{
						//Now calculate the value of the change
						ArrayList<Target> pathwithNoInfo=(ArrayList)currentPath.clone();
						Target newGoal=goals.get(firstTarget).clone();
						newGoal.value+=(directionFirst*Settings.jumpValue);				
						MainProgram.writeLog.writeln("-> Target "+newGoal.goalID+" changed value to: "+newGoal.value);
						pathwithNoInfo.set(pathwithNoInfo.indexOf(goals.get(firstTarget)),newGoal);
						newGoal=goals.get(secondTarget).clone();
						newGoal.value+=(directionSecond*Settings.jumpValue);				
						MainProgram.writeLog.writeln("-> Target "+newGoal.goalID+" changed value to: "+newGoal.value);
						pathwithNoInfo.set(pathwithNoInfo.indexOf(goals.get(secondTarget)),newGoal);
						ArrayList<Position> expectedmoves=expectedMoves(position,pathwithNoInfo.get(0));
						int currentValue=0;
						MainProgram.writeLog.writeln("Number of possible moves from ("+position.xPos+","+position.yPos+") to ("+pathwithNoInfo.get(0).position.xPos+","+pathwithNoInfo.get(0).position.yPos+") over the next game round: "+expectedmoves.size());
						if(expectedmoves.size()>1)
						{
							//TODO handle the case where we actually get to the goal over next move
							// Maybe handle it in the getValue function
							currentValue=(getValue(pathwithNoInfo,expectedmoves.get(0),time+1,true)+getValue(pathwithNoInfo,expectedmoves.get(1),time+1,true))/2;
						}
						else currentValue=getValue(pathwithNoInfo,expectedmoves.get(0),time+1,true);

						ArrayList<Target> pathwithInfo=bestPath(pathwithNoInfo,position,time);
						int newValue=getValue(pathwithInfo,position,time,true);
						int changeValue=(newValue-currentValue);
						if(changeValue>0) System.out.println("Value for the pair: "+firstTarget+","+secondTarget+" is: ("+newValue+"-"+currentValue+")="+changeValue);
						MainProgram.writeLog.writeln("Value for the pair: "+firstTarget+","+secondTarget+" is: ("+newValue+"-"+currentValue+")="+changeValue);
						if(changeValue>Settings.cost)
						{
							ChangesSet change=new ChangesSet();
							ChangeInTarget changeInTarget1=new ChangeInTarget(goals.get(firstTarget),directionFirst);
							ChangeInTarget changeInTarget2=new ChangeInTarget(goals.get(secondTarget),directionSecond);
							change.changes.add(changeInTarget1);
							change.changes.add(changeInTarget2);
							change.value=changeValue;
							changes.add(change);
						}
					}
				}
			}
		}
		return changes;
	}
	
	public void printChanges(ArrayList<ChangesSet> changes)
	{
		System.out.println("Changes that will have a positive impact:");
		for(int i=0;i<changes.size();i++)
		{
			Target goal1=changes.get(i).changes.get(0).goal;
			Target goal2=changes.get(i).changes.get(1).goal;
			System.out.println("("+goal1.goalID+","+goal2.goalID+")"+changes.get(i).value);		
		}
		System.out.println("Total changes to be reported: "+changes.size());
	}
	
	public void printProblem2File(int time)
	{
		MainProgram.writeLog.writeln("Current Problem:");
		MainProgram.writeLog.writeln("Target,xPos,yPos,value,decrease,precedence");
		for(int i=0;i<goals.size();i++)
		{
			Target goal=goals.get(i);
			MainProgram.writeLog.writeln(goal.goalID+","+goal.position.xPos+","+goal.position.yPos+","+(goal.value-goal.marginalValueDecrease*time)+","+goal.marginalValueDecrease);
		}
	}
	
	public void printGoals2File(ArrayList<Target> goals,int time)
	{
		MainProgram.writeLog.writeln("Target,xPos,yPos,value,decrease,precedence");
		for(int i=0;i<goals.size();i++)
		{
			Target goal=goals.get(i);
			MainProgram.writeLog.writeln(goal.goalID+","+goal.position.xPos+","+goal.position.yPos+","+(goal.value-goal.marginalValueDecrease*time)+","+goal.marginalValueDecrease);
		}
	}
	
	public String path2String(ArrayList<Target> path)
	{
		String result="";
		for(int i=0;i<path.size();i++)
			result=result+"->"+path.get(i).goalID;
		return result;
	}
	
}

